package demo.hw;

import java.util.*;

public class _跳马 {
    public static void main(String[] args) {
        /**
         * 输入m和n两个数，m和n表示一个m*n的棋盘。棋盘中存在数字和"."两种字符，
         * 如果是.表示该位置为空的，是数字表示为该马能走的最大步数。
         * 例如棋盘内某个位置一个数字为k，表示该马只能移动1~k步的距离。
         * 棋盘内的马移动类似于中国象棋日中的马移动，先在水平或者垂直方向上移动一格，然后再将其移动到
         * 对角线位置。
         * 棋盘内的马可以移动到同一个位置，同一个位置可以有多匹马。
         * 请问能否将棋盘上所有的马移动到同一个位置，若可以请输入移动的最小步数。若不可以输出0。
         * 输入描述
         * 输入m和n两个数，m和n表示一个m*n 的棋盘。输入棋盘内的数据。
         * 输出描述
         * 能否将棋盘上所有的马移动到同一个位置，若可以请输入移动的最小步数。若不可以输出0。
         * 示例1：
         * 输入
         * 3 2
         * . .
         * 2 .
         * . .
         * 输出
         * 0
         * 输入
         * 3 5
         * 4 7 . 4 8
         * 4 7 4 4 .
         * 7 . . . .
         * 输出
         * 17
         */
        int m = 3, n = 5;
        String[][] board = {
                {"4", "7", ".", "4", "8"},
                {"4", "7", "4", "4", "."},
                {"7", ".", ".", ".", "."}
        };
        //收集所有马的能力 (i,j,k) 9匹马
        List<int[]> horses = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!board[i][j].equals(".")) {
                    horses.add(new int[]{i, j, Integer.parseInt(board[i][j])});
                }
            }
        }

        // 每匹马进行bfs，计算到各点的最短步骤
        int[][][] dist = new int[horses.size()][m][n];
        // dist[horsesIdx][x][y]
        // 第一维: 表示马的索引
        // 第二维x: 棋盘的行坐标
        // 第二维y: 棋盘的列坐标
        // 值: 第horsesIdx匹马到达位置(x,y)的最短步骤
        for (int i = 0; i < horses.size(); i++) {
            for (int x = 0; x < m; x++) {
                Arrays.fill(dist[i][x], Integer.MAX_VALUE); // 初始化表示所有位置不可达
            }
            bfs(horses.get(i), dist[i], m, n);
        }

        // 寻找所有马能到达的位置，并计算最小总步数
        int min = Integer.MAX_VALUE;
        for (int x = 0; x < m; x++) {
            for (int y = 0; y < n; y++) {
                int total = 0;
                for (int i = 0; i < horses.size(); i++) {
                    if (dist[i][x][y] == Integer.MAX_VALUE) {
                        total = Integer.MAX_VALUE; // 无穷大表示不可达
                        break;
                    }
                    total += dist[i][x][y];
                }
                if (total < min) {
                    min = total;
                }
            }
        }
        System.out.println(min == Integer.MAX_VALUE ? 0 : min);
    }

    // 马的8种固定日字走法
    static int[][] dirs = {
            {1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}
    };

    // bfs计算单匹马到所有位置的最短步数
    private static void bfs(int[] horse, int[][] dist, int m, int n) {
        Queue<int[]> queue = new LinkedList<>();

        int startX = horse[0], startY = horse[1], k = horse[2];
        dist[startX][startY] = 0;
        queue.offer(new int[]{startX, startY});

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();

            int x = curr[0], y = curr[1];

            int currStep = dist[x][y];

            // 到达最大步数，不在继续移动
            if (currStep >= k) {
                continue;
            }
            // 尝试8个日字方向
            for (int[] dir : dirs) {
                int nx = x + dir[0];
                int ny = y + dir[1];

                // 检查边界
                if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                    // 更新最短距离
                    if (currStep + 1 < dist[nx][ny]) {
                        dist[nx][ny] = currStep + 1;
                        queue.offer(new int[]{nx, ny});
                    }
                }
            }
        }
    }
}
